/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
export var findTheWinner = function (n, k) {
  const members = new Array(n).fill(0).map((v, idx) => idx + 1)
  while (members.length > 1) {
    for (let i = 0; i < k - 1; i++) members.push(members.shift())
    members.shift()
  }
  return members[0]
}

/**
 * 官方题解(数学+迭代)
 * 约瑟夫环问题
   f(n, k) 
    = (f(n-1, k) % n ) ?  f(n-1, k) % n ) : n) 
    = (f(n-1, k) + k - 1) % n + 1
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
export var findTheWinner2 = function (n, k) {
  if (n === 1) {
    return 1
  }
  return ((k + findTheWinner2(n - 1, k) - 1) % n) + 1
}

export var findTheWinner3 = function (n, k) {
  let winner = 1
  for (let i = 2; i <= n; i++) {
    winner = ((k + winner - 1) % i) + 1
  }
  return winner
}
